package pATT.bNEdit.learning;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Vector;

import pATT.bNEdit.base.RedBayes;


@SuppressWarnings("unchecked")
public class AlgoritmoPC extends AlgoritmoAprendizajeEstructural{
  /**
   * Construye una instancia del algorimo PC con un grado de confianza
   * entre 0 y 4.
   */
    public AlgoritmoPC(int sig){
        super();
	Sxy=new Hashtable();
        significancia=sig;
    }
    /**
   * Construye una instancia del algorimo PC con un grado de confianza
   * por defecto de 4.
   */
    public AlgoritmoPC(){
      this(4);
    }

    private void incrementarFrecuencia(Hashtable H, String estado){
      if( H.containsKey(estado)){
		     int n=((Integer)H.get(estado)).intValue();
                     H.remove(estado);
		     n++;
		     H.put(estado,new Integer(n));
      }else
	H.put(estado,new Integer(1));
    }

    private void calcularFrecuencias(int X, int Y, Vector Z){
	Vector XY= new Vector();
        XY.addElement(new Integer(X));
	XY.addElement(new Integer(Y));
	Frecuencias=new Hashtable();
	for(int i=0; i<nroCasos; i++){

	    String clave=new String();
            String estX=obtenerEstado(i,X);
	    String estY=obtenerEstado(i,Y);

	    for(int j=0; j<Z.size(); j++)
                clave=clave+"*"+obtenerEstado(i,((Integer)Z.get(j)).intValue());

	    String cad=new String();
	    for(int j=0; j < XY.size(); j++)
                     cad=cad+"*"+obtenerEstado(i,((Integer)XY.get(j)).intValue());
	    if(Frecuencias.containsKey(clave)){
	        ((frecuencias)Frecuencias.get(clave)).NroOcurrencias++;
		 Hashtable H=((frecuencias)Frecuencias.get(clave)).frecX;
		 incrementarFrecuencia(H, estX);
		 H=((frecuencias)Frecuencias.get(clave)).frecY;
		 incrementarFrecuencia(H, estY);
		 Hashtable T=(Hashtable)((frecuencias)Frecuencias.get(clave)).Configuraciones;
	         if (T.containsKey(cad))
		  ((frecuenciasXY)T.get(cad)).nroOcurrencias++;
		 else
		    T.put(cad,new frecuenciasXY(estX,estY));
		}else{
               frecuencias ff=new frecuencias();
	       ff.frecX.put(estX,new Integer(1));
	       ff.frecY.put(estY,new Integer(1));
	       ff.Configuraciones.put(cad,new frecuenciasXY(estX,estY));
	       Frecuencias.put(clave,ff);
	    }
        }
    }

    private double CE(int X,int Y,Vector Z){
	        this.calcularFrecuencias(X,Y,Z);
		double resul=0;
                for(Enumeration e=Frecuencias.elements();e.hasMoreElements();){
		   frecuencias f=((frecuencias)e.nextElement());
                   int Nz=f.NroOcurrencias;
		   double val=0;
		   for(Enumeration c=f.Configuraciones.elements();c.hasMoreElements();)
		   {         frecuenciasXY fxy=((frecuenciasXY)c.nextElement());
			     String vx= fxy.varX;
			     String vy= fxy.varY;
			     int Nxyz=fxy.nroOcurrencias;
			     Integer a=(Integer)f.frecX.get(vx);
			     Integer b=(Integer)f.frecY.get(vy);
                             if( (Nxyz!=0)&&(a!=null)&&(b!=null) ){
			          int Nx=((Integer)f.frecX.get(vx)).intValue();
				  int Ny=((Integer)f.frecY.get(vy)).intValue();
	               		  double mult=(double)Nxyz*(double)Nz/((double)Nx*(double)Ny);
				  double term=(double)Nxyz/(double)Nz;
				  val=val + term*((double)Math.log(mult)/(double)Math.log(2.0));
			     }

		   };
		   resul=resul + val*(double)Nz/(double)nroCasos;
                }
	return resul;
    }

    //Obtiene los grados de libertad del conjunto Z
    private int getGradosLibertadZ(Vector Z){
      int res=1;
      for(int i=0; i<Z.size(); i++){
	      int z=((Integer)Z.get(i)).intValue();
	      res*=((Vector)estados.get(z)).size();
      }
      return res;
    }

    //Realiza el test de independencia
    private boolean I(int X, int Y, Vector Z, int gradoDeExactitud){
      double zAlpha[]={1.28,1.64,1.96,2.33,2.58};
      double entropia=CE(X, Y, Z);
      double chiCuadrado = ((double)2.0*(double)nroCasos)*entropia;

      int gradosDeLibertadX=((Vector)estados.get(X)).size()-1;
      int gradosDeLibertadY=((Vector)estados.get(Y)).size()-1;
      int gradosDeLibertadZ=getGradosLibertadZ(Z);
      int gL=gradosDeLibertadX * gradosDeLibertadY * gradosDeLibertadZ;

      double test = (double)(Math.pow((zAlpha[gradoDeExactitud] + Math.sqrt((2*gL)-1.0)),2))/(double)2.0;

      return !(chiCuadrado > test);
    }

    private void generarGrafoCompleto(){
        for(int i=0; i<Variables.size(); i++)
            for(int j=0; j<Variables.size(); j++)
                if(i!=j)
                    padres(i).addElement(new Integer(j));
    }

    private boolean buscarConjunto(int actual, Vector adyacentes, int X, int Y, int i, Vector S){
	if(S.size()==i){
            if( I(X,Y,S, significancia))
                 return true;
            else
                 return false;
        }
        else{
                for(int hijo=actual; hijo< adyacentes.size(); hijo++){
                     int variable=((Integer)adyacentes.get(hijo)).intValue();
		     if(variable!= Y){
                       S.addElement(new Integer(variable));
		       if(buscarConjunto(hijo+1,adyacentes,X,Y,i,S))
                           return true;
                       S.remove(S.size()-1);
                     }
                }
        return false;
        }
    }

    private String generarClave(int x, int y){
        String resp=new String();
        if(x<y)
            resp=String.valueOf(x)+String.valueOf(y);
        else
            resp=String.valueOf(y)+String.valueOf(x);
        return resp;
    }

    private void eliminarArco(int x, int y){
        for(int i=0; i<padres(x).size(); i++)
            if(((Integer)padres(x).get(i)).intValue()==y)
                padres(x).remove(i);
        for(int i=0; i<padres(y).size(); i++)
            if(((Integer)padres(y).get(i)).intValue()==x)
                padres(y).remove(i);
    }

    private boolean test( int i){
        for(int k=0; k<Variables.size(); k++)
            if(padres(k).size()<i) return false;
        return true;
    }

    //Encuentra el patron del grafo que se ajusta a la base de datos
    private void aprenderPatronGrafo(){
        this.generarGrafoCompleto();
        int i=0;
        Vector S;

	while(test(i)){
            for(int x=0; x < Variables.size(); x++){
                for(int y=0; y < padres(x).size(); y++){
                    S=new Vector();
                    int ady=((Integer)padres(x).get(y)).intValue();
                    if(buscarConjunto(0,padres(x),x,ady,i,S)){
                        Sxy.put(generarClave(x,y), S);
                        eliminarArco(x,y);
                    }
                }
            }
            i++;
        }
    }

    //Verifica si un Integer pertenece a un conjunto
    private boolean pertenece(Integer elem, Vector conj){
        for(int i=0; i<conj.size(); i++)
            if(((Integer)conj.get(i)).intValue()==elem.intValue())
                return true;
        return false;
    }

    //Verifica que el arco X - Y no sea dirigido
    private boolean noDirigida(int X, int Y){
      Integer x=new Integer(X);
      Integer y=new Integer(Y);
      if( (pertenece(x, padres(Y)) && (pertenece(y, padres(X)) )))
	  return true;
      return false;
    }

    //Verifica que la conexi?n X - Z - Y no sea dirigida
    private boolean ConexionVNoDirigida(int X, int Z, int Y){
      if( noDirigida(X,Z) && noDirigida(Y,Z) )
	  return true;
      return false;
    }

    private void eliminarArcoDirigido(int X, int Y){
      for(int i=0; i<padres(Y).size(); i++)
            if(((Integer)padres(Y).get(i)).intValue()==X){
	      padres(Y).remove(i);
	      return;
            }
    }

    //busca conjuntos de 2 adyacentes de la forma X - Z - Y de forma que si no estan dirigidos
    //los dirige de la forma X -> Z <- Y
    private void buscarConjuntoAdyacentes(int Z, Vector adyacentes){
      for(int i=0; i<adyacentes.size(); i++){
	int X=((Integer)adyacentes.get(i)).intValue();
        for(int j=i+1; j<adyacentes.size(); j++){
	  int Y=((Integer)adyacentes.get(j)).intValue();
	  Vector v=(Vector)Sxy.get(generarClave(X,Y));
	  if(v!=null){
	    if((ConexionVNoDirigida(X,Z,Y))&&!(pertenece(new Integer(Z), v))){
	      eliminarArcoDirigido(Z,X);
	      eliminarArcoDirigido(Z,Y);
	    }//if
	  }//if
        }//for
      }//for
    }

    //Orienta los arcos que puede
    private void encontrarArcos(){
      for(int i=0; i<Variables.size(); i++){
	this.buscarConjuntoAdyacentes(i,padres(i));
      }
    }

    //Devuelve true si quedan arcos por dirigir
    private void EncontrarRestoArcos(){
      Vector arcosNoDirigidos=new Vector();
      for(int i=0; i<Variables.size(); i++){
	for(int j=i+1; j<Variables.size(); j++){
	  if(this.noDirigida(i,j)){
	    eliminarArco(i,j);
	    arcosNoDirigidos.addElement(new Integer(i));
	    arcosNoDirigidos.addElement(new Integer(j));
	  }
	}
      }

      for(int i=0; i<arcosNoDirigidos.size()-1; i=i+2){
	int x=((Integer)arcosNoDirigidos.get(i)).intValue();
	int y=((Integer)arcosNoDirigidos.get(i+1)).intValue();
	if(!super.existeCamino(y,x))
	  padres(y).addElement(new Integer(x));
	else
	  padres(x).addElement(new Integer(y));
      }
    }

    /**
     * Metodo para aprender la estructura de una red bayesiana en base a un archivo
     * aplicando el algoritmo PC
     * @param nombreArchivo nombre del archivo origen
     */
    public RedBayes aprenderEstructura(String nombreArchivo){
        cargarDesdeArchivo(nombreArchivo);
	this.aprenderPatronGrafo();
	this.encontrarArcos();
	this.EncontrarRestoArcos();
        //Devuelve la red
        return crearRedBayesiana(nombreArchivo);
    }

    private Hashtable Sxy;
    private int significancia;
    private Hashtable Frecuencias;
    private class frecuencias{
         public frecuencias(){
	         NroOcurrencias=1;
	         Configuraciones=new Hashtable();
	         frecX=new Hashtable();
	         frecY=new Hashtable();
	     }
         public int NroOcurrencias;
	     public Hashtable Configuraciones;
	     public Hashtable frecX;
	     public Hashtable frecY;
   }
   private class frecuenciasXY{
         public frecuenciasXY(String ex,String ey){
	           varX=ex;
	           varY=ey;
               nroOcurrencias=1;
	     }
         public String varX;
	     public String varY;
	     public int nroOcurrencias;
   }
  }
